#if 0
#include <iostream>
using namespace std;
int nums[2000006];
int main() {
    int n;  cin >> n;
    int ret = 0;
    int tmp = 1;
    for (int i = 1; i <= n; i++) {
        cin >> nums[i];
        if (nums[i] - nums[i - 1] <= 8)
        {
            tmp++;
        }
        else {
            ret = max(ret, tmp);
            tmp = 1;
        }
    }
    ret = max(ret, tmp);
    cout << ret << endl;
}
// 2  0 -1 -1
// 0  0 -1 -1
// -1 0  0  0
// -1 -1 0  1
 // 4
 // // [[2,0,-1,-1],[0,0,-1,-1],[-1,0,0,0],[-1,-1,0,1]],4,4
// 2 0 0
// 0 0 0
// 0 0 1
int dp[15][15];
int ch_x[4] = { 0,0,-1,1 };
int ch_y[4] = { 1,-1,0,0 };
int ret = 0;
void bfs(vector<vector<int> >& CityMap, int n, int m, int x, int y) {
    queue<pair<int, int>> q1, q2;
    q1.emplace(x, y);
    while (q1.size()) {
        while (q1.size()) {
            auto [a, b] = q1.front();
            q1.pop();
            for (int i = 0; i < 4; ++i) {
                x = a + ch_x[i], y = b + ch_y[i];
                if (x < 0 || y < 0 || x >= n || y >= n || CityMap[x][y] == -1)
                    continue;
                if (CityMap[x][y] == 2)  ret++;
                else if (dp[x][y] == 0) {
                    q2.emplace(x, y);
                }
            }
            dp[a][b]++;
        }
        if (ret != 0)
            return;
        swap(q1, q2);
    }

}
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param CityMap int整型vector<vector<>>
     * @param n int整型
     * @param m int整型
     * @return int整型
     */
    int countPath(vector<vector<int> >& CityMap, int n, int m) {
        // write code here
        int x = 0, y = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++)
            {
                dp[i][j] = 0;
                if (CityMap[i][j] == 1) {
                    x = i, y = j;
                }
            }
        }
        ret = 0;
        bfs(CityMap, n, m, x, y);
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < m; j++)
                cout << dp[i][j] << ' ';
            cout << endl;
        }
        return ret;
    }
};
#endif
//int dp[15][15];
//int ch_x[4] = { 0,0,-1,1 };
//int ch_y[4] = { 1,-1,0,0 };
//int ret = 0;
//void bfs(vector<vector<int> >& CityMap, int n, int m, int x, int y) {
//    queue<pair<int, int>> q1, q2;
//    dp[x + 1][y + 1] = 1;
//    cout << x << ' ' << y << endl;
//    q1.emplace(x, y);
//    while (q1.size()) {
//        while (q1.size()) {
//            //auto [a, b] = q1.front();
//            int a = q1.front().first;
//            int b = q1.front().second;
//            q1.pop();
//            if (CityMap[a][b]!=1&&dp[a+1][b+1] != 0)
//                continue;
//            for (int i = 0; i < 4; ++i) {
//                x = a + ch_x[i], y = b + ch_y[i];
//                dp[a + 1][b + 1] += dp[x + 1][y + 1];
//                if (x < 0 || y < 0 || x >= n || y >= n || CityMap[x][y] == -1)
//                    continue;
//                if (dp[x + 1][y + 1] == 0) {
//                    q2.emplace(x, y);
//                    //dp[x + 1][y + 1] = dp[x][y + 1] + dp[x + 1][y] + dp[x + 2][y + 1] + dp[x + 1][y + 2];
//                }
//                if (CityMap[x][y] == 2)  ret = dp[x + 1][y + 1];
//            }
//        }
//        if (ret != 0)
//            return;
//        swap(q1, q2);
//    }
//
//}
//class Solution {
//public:
//    int countPath(vector<vector<int> >& CityMap, int n, int m) {
//        // write code here
//        int x = 0, y = 0;
//        for (int i = 0; i < n; i++) {
//            for (int j = 0; j < m; j++)
//            {
//                dp[i][j] = 0;
//                if (CityMap[i][j] == 1) {
//                    x = i, y = j;
//                }
//            }
//        }
//        ret = 0;
//        bfs(CityMap, n, m, x, y);
//        for (int i = 0; i <= n; i++)
//        {
//            for (int j = 0; j <= m; j++)
//                cout << dp[i][j] << ' ';
//            cout << endl;
//        }
//        return ret;
//    }
//};
int dx[] = { 0,0,-1,1 };
int dy[] = { -1,1,0,0 };
int x, y, rx, ry,n,m;
int bfs(vector<vector<int> >& CityMap) {
    vector<vector<int>> dist(n, vector<int>(m, -1));
    vector<vector<int>> cnt(n, vector<int>(m, 0));
    queue<pair<int, int>> q1, q2;    q1.emplace(x, y);
    dist[x][y] = 0;
    cnt[x][y] = 1;
    while (q1.size()) {
        while (q1.size())
        {
            int a = q1.front().first;
            int b = q1.front().second;
            q1.pop();
            //if (CityMap[a][b] != 1 && dist[a][b] != -1)  continue;
            for (int i = 0; i < 4; i++) {
                int _x = a + dx[i];
                int _y = b + dy[i];
                if (_x < 0 || _y < 0 || _x >= n || _y >= m || CityMap[_x][_y] == -1)     continue;
                if (dist[_x][_y] == -1 || dist[_x][_y] == dist[a][b] + 1) {
                    cnt[_x][_y] += cnt[a][b];
                    if (_x == 0 && _y == 0)
                        int aaaa = 10;
                    if (dist[_x][_y] == -1)
                    {
                        dist[_x][_y] = dist[a][b] + 1;
                        q2.emplace(_x, _y);
                    }
                }
            }
        }
        swap(q1, q2);
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++)
        {
            cout << dist[i][j] << ' ';
        }
        cout << endl;
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++)
        {
            cout << cnt[i][j] << ' ';
        }
        cout << endl;
    }
    return 0;
}
class Solution {
public:
    int countPath(vector<vector<int> >& CityMap, int _n, int _m) {
        n = _n, m = _m;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++)
            {
                if (CityMap[i][j] == 1)
                    x = i, y = j;
                if (CityMap[i][j] == 2)
                    rx = i, ry = j;
            }
        }
        return bfs(CityMap);
    }
};
int main() {
    vector<vector<int> >num = { {2,0,0},{0,0,1} };
    Solution().countPath(num, 2, 3);
    system("pause");
}
#include <iostream>
using namespace std;
int f[1003][105];
int g[1003][105];
int prices[1003];
int main() {
    int n, k;    cin >> n >> k;
    for (int i = 0; i < n; i++)
        cin >> prices[i];
    f[0][0] = -prices[0];
    for (int i = 1; i <= k; i++)
        f[0][i] = -10000000, g[0][i] = -1000000;
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j <= k; j++) {
            f[i][j] = max(f[i - 1][j], g[i - 1][j] - prices[i]);
            g[i][j] = g[i - 1][j];
            if (j >= 1) {
                g[i][j] = max(g[i][j], f[i - 1][j - 1] + prices[i]);
            }
        }
    }
    int ret = 0;
    for (int j = 1; j <= k; j++) {
        ret = max(ret, g[n][j]);
    }
    cout << ret << endl;
}